function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr
    } else {
        let midIndex = Math.floor(arr.length / 2);
        let left = arr.slice(0, midIndex);
        let right = arr.slice(midIndex, arr.length);
        return merge(mergeSort(left), mergeSort(right))
    }
};

function merge(left, right) {
    let result = [];
    let i = 0;
    let j = 0;
    while (i < left.length && j < right.length) {
        left[i] < right[j] ? result.push(left[i++]) : result.push(right[j++])
    }
    while (i < left.length) {
        result.push(left[i++])
    }
    while (j < right.length) {
        result.push(right[j++])
    }
    return result;
}

// 先拆成单个元素的数组，再边比较便合并
// 时间复杂度nlogn
arr = [1, 6, 5, 2, 8, 0];
console.log(mergeSort(arr));